perm filename BIN[0,BGB] blob
sn#116834 filedate 1974-08-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00011 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00005 00002 {F3⊂C<Nα POLYHEDRON INTERSECTION.λ30P60I425,0JCFA} SECTION 5.
C00008 00003
C00010 00004 {I110,0}⊂5.1 Intersection Geometry.⊃
C00014 00005 {I110,0}⊂5.2 Intersection Topology.⊃
C00018 00006
C00021 00007 ~Fix up step-1~ places vertex and wing pointers in all the
C00024 00008 {FCJC} FIGURE 5.5 - EXAMPLE OF A FACE HOLE FIXUP. {JUFA
C00028 00009 ⊂5.4 Face Convexity Coercion.⊃
C00031 00010 ⊂5.5 Body Cutting.⊃
C00034 00011 ⊂5.6 Performance and Related Work.⊃
C00036 ENDMK
C⊗;
{F3;⊂C;<N;α POLYHEDRON INTERSECTION.;λ30;P60;I425,0;JCFA} SECTION 5.
{JCFD} POLYHEDRON INTERSECTION.
{λ10;W250;JAFA}
5.0 Introduction to Polyhedron Intersection.
5.1 Intersection Geometry.
5.2 Intersection Topology.
5.3 Special Cases of Intersection.
5.4 Face Convexity Coercion.
5.5 Body Cutting.
5.6 Performance and Related Work.
{λ30;W0;I950,0;JUFA}
⊂5.0 Introduction to Polyhedron Intersection.⊃
The intersection, union, and set differences of two solid
polyhedra can be computed by combining a body intersection procedure
called BIN with the EVERT primitive, as Figure 5.1 illustrates. The
body intersection procedure is important for three reasons: first, it
is a general and conceptually elegant construction operator; second,
it can be used for spatial modeling in collision detection and
trajectory planning for manipulators and vehicles; and third, it can
be used to localize an object in 3-D space from a sequence of
silhouette views. The intersection algorithm consists of two parts:
first, there is a geometric part in which all the faces and edges are
compared with each other for potential face/edge intersections called
piercing points; and second, there is a topological part in which the
results are "copied off" of the given polyhedra; the results may
consist of zero, one or many polyhedra. In the following, the term
"operands" refers to the sets of polyhedra given to BIN as arguments
and the term "result" refers to the set (possibly empty) of polyhedra
produced by BIN.{Q}
{I130,0;FCJC} FIGURE 5.1 - POLYHEDRON INTERSECTION, UNION AND SUBTRACTION.
{H3;X0.61;
I100,630-338;
⊗BIN1.PLT;
I∂110,0;JCFA} TWO POLYHEDRA{
I100,630-338;
I∂580,0;JCFA} STAR AND CYLN{
I650,1;
⊗BIN2.PLT;I∂0,∂630;⊗BIN3.PLT;
I∂110,0;W0,630;JCFA} INTERSECTION {I∂0,630;W630,1260;JCFA} UNION{
I650,1;
I∂580,0;W0,630;JCFA} BIN(STAR,CYLN){I∂0,630;W630,1260;JCFA
} EVERT(BIN(EVERT(STAR),EVERT(CYLN))) {W0,1260;
I1200,1;
⊗BIN4.PLT;I∂0,∂630;⊗BIN5.PLT;
I∂110,0;W0,630;JCFA} SUBTRACTION{I∂0,630;W630,1260;JCFA} SUBTRACTION{
I1200,1;
I∂580,0;W0,630;JCFA} BIN(EVERT(STAR),CYLN){I∂0,630;W630,1260;JCFA
} BIN(STAR,EVERT(CYLN)){W0,1260;JUFAQ}
{I110,0;}⊂5.1 Intersection Geometry.⊃
Conceptually, the geometric part of the polyhedron intersection algorithm,
BIN, consists of comparing each face of one operand
with every edge of the other operand and vice versa. In practice
the potentially N-squared compares are avoided by using the same
recursive window partition sort that was used in the hidden line
eliminator, OCCULT, Section 4.3. Ignoring the recursive windowing for
a moment, the innermost face-edge compare of BIN consists of four
steps: opposition, intersection, enclosure and fission.
{JCFC} FIGURE 5.2 - FACE PIERCING GEOMETRY.
{JUFA;I∂95,0;X1.0;I∂0,315;H4;*FIG52.1;H1;*FIG52.2;I∂15,310;}F{
I∂-15,805;H4;*FIG52.3;H1;*FIG52.4;I∂15,800;}F{I∂85,300;}E{I∂0,1005;}E{I∂120,0;
W0,630;JCFA} Piercing Point Within F. {I∂0,630;
W630,1260;JCFA} Piercing Point Outside F. {W0,1260;λ30;I∂25,0;JUFA}
~<Opposition Test>~. Given a face F and an edge E, first,
the endpoints of the edge are checked to see whether they are in
opposite halfspaces with respect to the plane of the face. In terms
of vector geometry, the dot product of the face vector and each
vertex vector is taken and the signs compared; different signs
indicate that the vertices are in different halfspaces. The
opposition test requires six multiplications. ~<Intersection Locus>~.
The locus of the point where the edge pierces the plane of the face
is computed (four multiplications).
~<Enclosure Test>~. Next the edge is tested to see if
it actually passes thru the interior of the face. In BIN, this test
exploits the face convexity restriction. The test consists of
crossing neighboring pairs of vectors radiating from the face-plane
piercing-point to each vertex of the given face and testing for a
sign change, Figure 5.2. Since only one component of the
cross product needs to be evaluated, the test
requires only two multiplications per
edge of the face whoes plane is pierced.
~<Edge Fission>~. If the edge pierces
the face, then the edge is split (using the ESPLIT and BLED routines)
forming a new vertex, called a face piercing vertex. A temporary
link of the vertex node (field CW, left half of word 7) is set to
point at the face that was pierced and the PED link of the new vertex
is set to point at the one of its two edges that is external to the
surface.
{I110,0;}⊂5.2 Intersection Topology.⊃
After the face-piercing vertices have been made (assuming no
pathological cases, Section 5.3), the edges and vertices of the
result can be created in relation to the faces, edges, and vertices
of the operands. The relation between the operands and the results is
established in terms of two kinds of edges: interior edges and
surface edges as illustrated in Figure 5.3. Surface edges correspond
to the intersections of pairs of operand faces and interior edges
correspond to edges of one operand that are enclosed inside the surface
of the other operand. Surface edges always form connected loops. In
Figure 5.3, two solid prisms are being intersected, on the left the
surface edges of the intersection (a surface loop) is intensified in
heavy lines, on the right the interior edges are intensified.
{JCFC} FIGURE 5.3 - THE SURFACE AND INTERIOR EDGES OF INTERSECTION.
{JUFA;I∂200,315;X0.6;H4;*53.2;H1;*53.1;I∂0,945;H4;*53.3;H1;*53.1;*53.2;
I∂240,60;JAFA} Surface Edges of Intersection. {
I∂0,690;JAFA} Interior Edges of Intersection. {JUFA}
In similar fashion there are surface vertices and interior
vertices of the result. Each face-piercing vertex of the operands has
a corresponding surface vertex in the result which is always a
trihedral corner. The operand/result correspondence is maintained in
a temporary link field named ALT; the alternate vertices and edges
that belong to the result are created by two topological trace
routines: the make surface, MKSURF routine, which creates surface
edges and vertices of the result by tracing surface loops starting
from an "un-ALTered" face piercing vertex. At each face-piercing
vertex, MKSURF applies the ETRACE routine to the single interior edge
of the trihedral corner. ETRACE creates edges and vertices interior
to the result by tracing the edge graph bounded by face-piercing
vertices. The new result edges are temporarily linked (PFACE and
NFACE) to the old operand faces. The MKSURF and ETRACE routines are
followed by three steps that fix up the surface wings, interior wings
and face nodes so that a complete winged edge polyhedral result is
legally formed.
The interior trace routine is trivial - all the links are
readily accessed using the ECCW and OTHER primitives on the operand
polyhedra. The surface trace routine is made easy by implementing a
procedure, NEXTPV, to retrieve the next face-piercing vertex about a
surface loop. The NEXTPV procedure, given below, is based on the
obseravtion that the intersection of two convex faces is one line
segment and either one face is pierced twice by two different edges
of the other face; or each face is pierced once by one edge of the
other face, Figure 5.4.
{JCFC} FIGURE 5.4 - FETCH NEXT FACE-PIERCING VERTEX.
{JUFA;I∂120,0;X0.7,0.4;
I∂0,315;H1;*54.1;H4;*54.2;
↓;I∂0,∂-96;C6;} V1{↑
↓;I∂-1,∂223;C6;I∂10,∂-45;}V2{↑
↓;I∂-100,∂-120;}F1{↑
↓;I∂50,∂100;}F2{↑
I∂0,945;H1;*54.3;H4;*54.4;
↓;I∂5,∂-150;C6;} V1{↑;
↓;I∂12,∂239;C6;I∂10,∂-45;}V2{↑;
↓;I∂-100,∂-85;}F1{↑;
↓;I∂50,∂-100;}F2{↑;
I∂150,0;W0,630;JCFA} Edge of F1 pierces F2 at V2. {I∂0,630;
W630,1260;JCFA} Edge of F2 pierces F1 at V2. {W0,1260;λ10;I∂25,0;JUFA}
{λ10;JAF3;W100;}
COMMENT RETURN THE NEXT FACE PIERCING VEXT OF A SURFACE LOOP;
INTEGER PROCEDURE NEXTPV (INTEGER F2,V1);
BEGIN "NEXTPV"
INTEGER F1,V2;
F1 ← CW(V1); COMMENT FACE PIERCED BY V1;
COMMENT DOES AN EDGE OF F1 PIERCE F2 AT THE OTHER PIERCE-VERTEX V2;
E ← E0 ← PED(F1);
DO IF F2 = CW(V2←VCCW(E,F1)) THEN RETURN(V2) UNTIL E0 = (E←ECCW(E,F1));
COMMENT DOES AN EDGE OF F2 PIERCE F1 AT THE OTHER PIERCE-VERTEX V2;
E ← E0 ← PED(F2);
DO IF F1 = CW(V2←VCCW(E,F1)) ∧ V2≠V1 THEN RETURN(V2) UNTIL E0 = (E←ECCW(E,F2));
COMMENT FATAL CONSISTENCY ERROR - SOMETHING WRONG IN FACE/EDGE COMPARE PASS;
RETURN(0);
END "NEXTPV";{λ30;JUFA;W0;}
~Fix up step-1~ places vertex and wing pointers in all the
interior edges. An interior edge is distinguished by its non-zero
ALT link. The new vertices are provided with a first edge, PED(VNEW),
if it be lacking. ~Fix up step-2~ wings together the surface vertex
tridedral corners. Since by good luck all surface vertices are
necessarily trihedral, the edges can be passed to the WING primitive
for oriented linking, in any order. The two surface wings of a
surface vertex were stored in the NED and PED links by MKSURF; the
inward wing can be retrieve as the PED(ALT(U)). Surface vertices are
distinguished by their ALT vertex being marked as a piercing vertex.
~Fix up step-3~
replaces the alien faces of the result with native faces. This is
done by scanning the edge ring of the body, testing the two faces of
each edge to see if they belong to the result body, and if a face
doesn't belong it is replaced by a new one. Face replacement, as
ususal, requires clocking around a face perimeter and changing the
appropriate face link in each edge. A final marking trace assigns one
body node to each separate connected graph of faces, edges and
vertices.
{FCJC} FIGURE 5.5 - EXAMPLE OF A FACE HOLE FIXUP. {JUFA
H2;X0.41;I∂0,0;⊗55.1;I∂0,420;⊗55.2;I∂0,840;⊗55.3;I∂350,0;}
⊂5.3 Special Cases of Intersection.⊃
In order of difficulty from easy to hard, the four special
cases that must be handled are non-intersection, extremely short
edges, face holes and coincident entities. ~<Non-Intersection>~.
When the face-edge compare (by recursive window space sort) returns
no piercing points, it implies that the surfaces of the given
polyhedra do not intersect and that a further test is needed to
determine whether the operands are disjoint (and so the intersection
be empty) or whether one operand contains the other. ~<Face Holes>~.
Because EVERTed solids are allowed, one polyhedron can cut a hole in
a face of the other without intersecting any of the edges of that
face, which would fool the copy-trace. So as a preliminary step to
BIN, all the surface loops are traced and checked to make certain
they cross more than one face. If a one face surface-loop is found,
the face is pyramided to a vertex interior to the surface-loop. A
face hole fix up is illustrated in Figure 5.5, the middle panel of
the figure shows that two faces of the cubic prism were pyramided,
the right panel of the figure shows the result after face-convexity
coercion. ~<Short Edges>~. An application of BIN can create edges
with almost zero length, which require an extra pass to find and
delete. ~<Coincident Entities>~. An occasional edge that lies
exactly in the plane of a face can be nudged off the plane a little
resulting in extremely short edges which are later removed. Although
it is meaningful to try to intersect polyhedra which have many faces,
edges and vertices that are exactly coincident, the present
implementation loses track of interior and exterior when too many
nearly zero length edges are made.
⊂5.4 Face Convexity Coercion.⊃
Since, both the body intersecter, BIN, and the hidden line
eliminator, OCCULT, are restricted to convex faced polyhdera; it is
essential to have a routine that detects and subdivides the concave
faces of a given polyhedron. The make convex routine, MKCNVX, reduces
the concave faces of a body into reasonably small
number of convex faces. The method
consists of two steps: first, the face is broken down into triangles
and second, the longest unnecessary newly made edges are removed. The
reduction to triangles step is recursive: the pointiest extrema
vertex of a face, V0, is lopped off, if no other vertices of the face
are on the same side of the line segment between V0's immediate
neighboring vertices: OTHER(ECCW(V0,F),V0) and OTHER(ECW(V0,F),V0).
Otherwise the face is split, MKFE, using the vertex closest to V0
that violates V0's potential lop line. An extrema vertex is one that
touchs the smallest circumscribed rectangle whose sides are parellel
to the coordinate axes; the pointiest vertex is the one with the
largest cosine.
{I∂25,0;FCJC} FIGURE 5.6 - EXAMPLES OF FACE CONVEXITY COERCION. {JUFA
X0.246;H2;I∂-20,0;⊗56.1;I∂0,∂252;⊗56.2;I∂0,∂252;⊗56.3;I∂0,∂252;⊗56.4;
I∂0,∂252;⊗56.5;I∂190,0;JUFA}
⊂5.5 Body Cutting.⊃
Body cutting is the operation of dividing an arbitrary
polyhedron into sets of parts above and below a given cutting plane,
as has already been illustrated in Figure 3.8. Although body cutting
might be done by subtracting a very large thin rectangular prism, the
process is sufficiently important to merit a separate implementation
which nevertheless resembles the subtraction. First, all the edges of
the given body are compared with the given cutting plane and piercing
vertices are formed in pairs (one vertex for each side of the cut).
Between the cutting-plane vertex-pairs are zero length edges which
are placed into a special temporary list. Next, pairs of
cutting-plane vertices (belonging to the same face and destined to be
in the same half-space) are MKFEed together splitting the faces with
cutting-plane edge pairs (one edge for each side of the cut). Between
the cutting-plane edge-pairs are zero area faces. Finally all the
zero length cutting plane edges are KLFEed if their PFACE and NFACE
are different or UNGLUEed if their PFACE and NFACE are the same. In
this circumstance an edge having the same NFACE and PFACE is a wasp
edge. The simplicity of the body cutting implementation is do to the
power of the UNGLUE Euler primitive.
⊂5.6 Performance and Related Work.⊃
Curious to relate, I have found no example in the literature
of a general polyhedron intersection method. Maruyama's (72) method
is a collision detector rather than a intersector, because he does
not attempt to generate the polyhedra of intersection; however, his
algorithm does resemble the geometric first phase of BIN and might
have been extended for generating new solids. The intersection
methods of Braid (73) are restricted to particular combinations of
six volume elements which comprise a useful subset of cases for
mechanical drawing.
The version of BIN is implemented on a PDP-10 (with 2
microsecond core memory) can construct the intersection of simple
objects such as a pair of cubes in less than a quarter of a second;
the intersection of a couple of twenty sided cylinders in about two
seconds; the intersection of two horse silhouette cones takes
(chapter 9) about fifteen seconds; and the intersection of two
silhouette cone intersections can take up to a minute.